package map_set;

import java.util.HashSet;
import java.util.Set;

//287. 寻找重复数
//public class Num287_findDuplicate {
//    public int findDuplicate(int[] nums) {
//        Set<Integer> set = new HashSet<>();
//        for (int i : nums){
//            if (set.contains(i)){
//                return i;
//            }else {
//                set.add(i);
//            }
//        }
//        return -1;
//    }
//}

/**
 * 双指针
 */
public class Num287_findDuplicate {
    public int findDuplicate(int[] nums) {
        int slow = 0 ;
        int fast = 0;
        while (true){
            slow = nums[slow];//纵走一步
            fast = nums[nums[fast]];
            if (fast == slow){
                break;
            }

        }
         fast = 0 ;
        while (fast != slow){
            slow = nums[slow];//走一步
            fast = nums[fast];//
        }
        return slow;

    }

}
